{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# pyalg数据结构和算法设计\n",
    "1、主要参考《Data Structures and Algorithms with Object-Oriented Design Patterns in Python》Bruno R. Preiss B.A.Sc., M.A.Sc., Ph.D., P.Eng.及opus7实现和《数据结构和算法-面向对象的C++设计模式》\n",
    "\n",
    "2、算法导论\n",
    "\n",
    "3、编写pyalg的目的：\n",
    "   > 学习如何OOP\n",
    "    \n",
    "   > 学习如何设计一个库\n",
    "   \n",
    "   > 学习python语法特性，尤其是2.7及以后的版本"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 如何OOP\n",
    "- 归纳（抽象）\n",
    "\n",
    "- 衍生"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 设计库\n",
    "- 设计思路\n",
    "    - ADT抽象数据型，提供接口，不提供实现\n",
    "    - ADT抽象数据型，通常实现为抽象类，不能实例化\n",
    "    - ADT抽象数据型，库只提供一两种其子类的实现，库使用者可以自行扩充，更大的灵活性\n",
    "    - 提供不同的ADT抽象数据型，模块化设计\n",
    "\n",
    "- 模块化\n",
    "    - 分配器：（对容器来说，一级抽象，“物理”结构）\n",
    "        - ADT数组，它是一种具备检索和存储的抽象数据型，跟通常意义上理解的数组“一片连续的内存区域”不一样，这已经涉及到了它的具体实现，你也可以使用链表等来模拟ADT数组，但它本身不一定是数组。\n",
    "            - Create创建\n",
    "            - Store存储, [ ] = value\n",
    "            - Retrieve检索, value = [ ]\n",
    "        - 链表类型\n",
    "            - Create创建\n",
    "            - \n",
    "        - ADT链接矩阵\n",
    "            - Create创建\n",
    "            - Store存储, [ , ] = value\n",
    "            - Retrieve检索, value = [ , ]\n",
    "            - Transpose转置\n",
    "            - Multiply相乘\n",
    "            - Add相加\n",
    "        - 链接表\n",
    "    - 容器：（对分配器进一步封装，二级抽象，逻辑结构）\n",
    "        - 内置一个分配器对象\n",
    "        - 内置一个默认迭代器，同时需要一个替换迭代器的接口\n",
    "        - 不同的ADT容器，不同的接口\n",
    "            - ADT栈\n",
    "                - Create创建栈\n",
    "                - Push入栈\n",
    "                - Pop出栈\n",
    "                - GetTop获取栈顶元素\n",
    "                - IsEmpty栈是否为空\n",
    "                - IsFull栈是否满\n",
    "                - Delete销毁栈\n",
    "            - ADT队列\n",
    "                - Create创建队列\n",
    "                - Enqueue入队列\n",
    "                - Dequeue出队列\n",
    "                - GetHead获取队列头元素\n",
    "                - GetTail获取队列尾元素\n",
    "                - Delete销毁队列\n",
    "            - ADT树\n",
    "                - Create创建树\n",
    "                - GetCount获取树节点数\n",
    "                - GetDegree获取树的度\n",
    "                - GetHeight获取树的高度\n",
    "                - GetKey获取节点的Key\n",
    "                - Delete销毁树\n",
    "            - 图\n",
    "            - 堆\n",
    "\n",
    "         *容器和分配器之间关系非常密切，它们如何搭配？*\n",
    "         \n",
    "         1）分配器必须能够满足ADT接口实现，需要考虑实现上难易程度，性能和效率\n",
    "         \n",
    "         2）有些容器更适合与某种分配器搭配，例如队列与随机存储类型、队列与链式类型、图与链接矩阵、图与连接表\n",
    "         \n",
    "         3）有时一个容器可以和多种分配器搭配，但要看容器的哪种操作比较多，进行合理选择\n",
    "            \n",
    "    - 迭代器：\n",
    "        - 迭代器是封装了对分配器的访问，尤其是不同容器形态，按照线性迭代的方式访问\n",
    "        - 每个迭代器根据容器的不同，有自己的迭代算法，由next函数实现，在基类抽象类中定义为抽象函数\n",
    "        - \\__iter\\__直接返回self迭代器本身，每个迭代器都一样\n",
    "        - 在创建时需要传入容器对象，因为在next中，需要访问到容量里的分配器数据\n",
    "        - 迭代器通过传入的容器对象接触分配器，根据分配器的特点和类型，在next中实现算法\n",
    "    - 适配器：\n",
    "        - 容器适配器：\n",
    "            - 创建时需要传入容器对象\n",
    "            - 对容器的操纵分配器的接口进行限制\n",
    "    - 算法："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 语法特性\n",
    "- 元编程 - 元类（语法，见[python元编程](..\\python语法\\python元编程.ipynb)）\n",
    "    - abc.ABCMeta和@abstractmethod组合使用，使类变为抽象类，无法实例化。\n",
    "    \n",
    "- 装饰器和描述器（语法，见[python描述器](..\\python语法\\python描述器.ipynb)）\n",
    "    - @property，使isXXX这类函数和一些统计类的接口，直接变为属性，而不是函数调用的方式，这样更加简化和简洁\n",
    "    - @staticmethod\n",
    "    - @abstractmethod\n",
    "   \n",
    "- 命名空间 - 模块化设计（语法，见[python命名空间](..\\python语法\\python命名空间.ipynb)）\n",
    "       \n",
    "    - alloc空间分配器\n",
    "       \n",
    "    - container容器\n",
    "    \n",
    "    - iterator迭代器\n",
    "    \n",
    "    - adapt适配器\n",
    "    \n",
    "    - alg算法\n",
    "       "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
